|
In mathematics, a universal graph is an infinite graph that contains ''every'' finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by R. Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family ''F'': that is, an infinite graph belonging to ''F'' that contains all finite graphs in ''F''. A universal graph for a family ''F'' of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in ''F''; for instance, every finite tree is a subgraph of a sufficiently large hypercube graph〔 〕 so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for ''n''-node trees with only ''n'' vertices and O(''n'' log ''n'') edges, and that this is optimal.〔.〕 A construction based on the planar separator theorem can be used to show that ''n''-vertex planar graphs have universal graphs with O(''n''3/2) edges, and that bounded-degree planar graphs have universal graphs with O(''n'' log ''n'') edges. Sumner's conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2''n'' − 2 vertices contains every polytree with ''n'' vertices as a subgraph.〔(Sumner's Universal Tournament Conjecture ), Douglas B. West, retrieved 2010-09-17.〕 A family ''F'' of graphs has a universal graph of polynomial size, containing every ''n''-vertex graph as an induced subgraph, if and only if it has an adjacency labelling scheme in which vertices may be labeled by ''O''(log ''n'')-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in ''F'' may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.〔.〕 In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph. == References == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「universal graph」の詳細全文を読む スポンサード リンク
|